import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-23
 * Time:9:23
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Test {

    //完全二叉树
    public boolean isCompleteTree (TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(queue.peek()!=null){
            TreeNode cur=queue.poll();
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while (!queue.isEmpty()){
            if(queue.poll()!=null){
                return false;
            }
        }
        return true;
    }

    //层序遍历
    public List<List<Integer>> levelPrint(TreeNode root){
        List<List<Integer>> list= new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> l=new ArrayList<>();
            int size=queue.size();
            TreeNode cur=queue.peek();
            for (int i = 0; i < size; i++) {
                l.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                } if(cur.right!=null){
                    queue.offer(cur.right);
                }
                queue.poll();
            }
            list.add(l);
        }
        return list;

    }

    //判断是不是对称的
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isCompara(root.left,root.right);
    }
    public boolean isCompara(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if (left==null||right==null){
            return false;
        }
        if(right.val==left.val){
            return
            isCompara(left.left,right.right)&&
            isCompara(left.right,right.left);
        }
        return false;
    }

    //判断是不是高度平衡的树
    public boolean isBalanced(TreeNode root) {
        if(root==null) {
            return true;
        }
        return dHeight(root)>1;
    }
    public int dHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=dHeight(root.left);
        int right=dHeight(root.right);
        //如果是负数就直接返回负数
        if(left==-1||right==-1||Math.abs(left-right)>1){
            return -1;
        }
        return left>right?left+1:right+1;
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        //判断根是空的
        if(pRootOfTree==null){
            return null;
        }
        TreeNode left=Convert(pRootOfTree.left);
        TreeNode right=Convert(pRootOfTree.right);
        //怎么返回
        if(left!=null&&right!=null){
            left.right=pRootOfTree;
            pRootOfTree.left=left;
            pRootOfTree.right=right;
            right.left=pRootOfTree;
            return right;
        }
        if(left==null){
            pRootOfTree.right=right;
            right.left=pRootOfTree;
            return pRootOfTree;
        }
            left.right=pRootOfTree;
            pRootOfTree.left=left;
            return pRootOfTree;

    }
    //公共祖先
    //1.子问题
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null||root==p||root==q){
                return root;
            }
            TreeNode left=lowestCommonAncestor(root.left,p,q);
            TreeNode right=lowestCommonAncestor(root.right,p,q);
            if(right!=null&&left!=null){
                return root;
            }
            if(right==null){
                return left;
            }
            return right;
       }
       //放两个栈
    public boolean search(TreeNode root,TreeNode cur,Stack<TreeNode> stack){
        //到头了

        if(root==null||cur==null){
            return false;
        }
        stack.push(root);
        //找到了
        if(root==cur){
            stack.add(root);
            return true;
        }
        boolean left=search(root.left,cur,stack);
        if(left){
            return true;
        }
        boolean right=search(root.right,cur,stack);
        //还没找到
        ////
        if(right){
            return true;
        }
            stack.pop();
            return false;
    }
//    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
//        Stack<TreeNode> stackp=new Stack<>();
//        Stack<TreeNode> stackq=new Stack<>();
//        search(root,p,stackp);
//        search(root,q,stackq);
//        int sizep=stackp.size();
//        int sizeq=stackq.size();
//        if(sizep>sizeq){
//            for (int i = 0; i < sizep-sizeq; i++) {
//                stackp.pop();
//            }
//            while(!stackp.isEmpty()){
//                if(stackp.peek()==stackq.peek()){
//                    return stackp.pop();
//                }
//                stackp.pop();
//                stackq.pop();
//            }
//        }else{
//            for (int i = 0; i < sizeq-sizep; i++) {
//                stackq.pop();
//            }
//            while(!stackp.isEmpty()){
//                if(stackp.peek()==stackq.peek()){
//                    return stackp.pop();
//                }
//                stackp.pop();
//                stackq.pop();
//            }
//        }
//        //这为什么一直要有
//        return root;
//    }
public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
    Stack<TreeNode> stackp=new Stack<>();
    Stack<TreeNode> stackq=new Stack<>();
    search(root,p,stackp);
    search(root,q,stackq);
    int sizep=stackp.size();
    int sizeq=stackq.size();
    if(sizep>sizeq){
        for (int i = 0; i < sizep-sizeq; i++) {
            stackp.pop();
        }
    }else{
        for (int i = 0; i < sizeq-sizep; i++) {
            stackq.pop();
        }
    }
    while(stackp.peek()!=stackq.peek()){
        stackp.pop();
        stackq.pop();
    }
    return stackq.peek();
}

}
